#pragma once

#include <algorithm>
#include <functional>
#include <memory>
#include <vector>
#include <unordered_set>


class ISet {
public:
	virtual ~ISet() { }

	virtual bool contains(int value) const = 0;

	virtual void foreach(std::function<void(int)> visitor) const = 0;

    virtual size_t byteSize() const = 0;
};


class UnorderedSet : public ISet {
public:
    template <class Sequence>
    explicit UnorderedSet(const Sequence& sequence)
      : set_(sequence.begin(), sequence.end())
    { }

    bool contains(int value) const
    {
        return set_.count(value) > 0;
    }

    void foreach(std::function<void(int)> visitor) const
    {
        for (auto it = set_.begin(); it != set_.end(); ++it) {
            visitor(*it);
        }
    }

    size_t byteSize() const
    {
        return (2*sizeof(void*) + sizeof(int)) * set_.size();
    }

private:
    std::unordered_set<int> set_;
};


class BitSet : public ISet {
public:
    template <class Sequence>
    explicit BitSet(const Sequence& sequence)
    {
        if (sequence.size() == 0) {
            offset_ = 0;
            return;
        }
        const auto minmax = std::minmax_element(sequence.begin(), sequence.end());
        offset_ = *minmax.first;
        bitset_.resize(*minmax.second - offset_ + 1, false);
        for (auto it = sequence.begin(); it != sequence.end(); ++it) {
            bitset_[*it - offset_] = true;
        }
    }

    bool contains(int value) const
    {
        return offset_ <= value &&
               value - offset_ <= bitset_.size() &&
               bitset_[value - offset_];
    }

    void foreach(std::function<void(int)> visitor) const
    {
        for (size_t index = 0; index < bitset_.size(); ++index) {
            if (bitset_[index]) {
                visitor(offset_ + index);
            }
        }
    }

    size_t byteSize() const
    {
        return sizeof(int) + bitset_.size() / 8;
    }

private:
    int offset_;
    std::vector<bool> bitset_;
};


std::unique_ptr<ISet> makeCompactSet(const std::vector<int>& sequence);
